package leetcode.D400.T337;

import util.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-22 18:21:55 星期二
 */

class Solution {
    // 如果不用map来记录，会超时，这里相当于空间换时间了
    Map<TreeNode, Integer> mapNotRob = new HashMap<>();
    Map<TreeNode, Integer> mapRob = new HashMap<>();

    public int rob(TreeNode root) {
        return Math.max(getTotal(root, false), getTotal(root, true));
    }

    private int getTotal(TreeNode root, boolean robbed) {
        if (root == null)
            return 0;
        if (robbed) {
            if(mapNotRob.containsKey(root))
                return mapNotRob.get(root);
            int notRob = getTotal(root.left, false) + getTotal(root.right, false);
            mapNotRob.put(root, notRob);
            return notRob;
        }
        int notRob = 0, rob = 0;
        if(mapNotRob.containsKey(root))
            notRob = mapNotRob.get(root);
        else {
            notRob = getTotal(root.left, false) + getTotal(root.right, false);
            mapNotRob.put(root, notRob);
        }
        if(mapRob.containsKey(root))
            rob = mapRob.get(root);
        else {
            rob = getTotal(root.left, true)+getTotal(root.right, true)+root.val;
            mapRob.put(root, rob);
        }
        return Math.max(notRob, rob);
    }
}